//
// Description: 802. 找到最终的安全状态
// Created by Loading on 2021/8/5.
//

#include <bits/stdc++.h>

using namespace std;

/* DFS */
vector<int> eventualSafeNodes_DFS(vector<vector<int>> &graph) {
    /* 某节点路径中走到了曾经到达过的点，则不安全 */

    // 标记节点状态，0：未遍历；1：路径中出现过；2：安全
    vector<int> status(graph.size());

    function<bool(int)> dfs = [&](int v) {
        if (status[v] != 0) {
            return status[v] == 2;
        }
        // 先将节点状态置为 出现过
        status[v] = 1;
        // 检查路径节点是否全都安全
        bool check = all_of(graph[v].begin(), graph[v].end(), [&](int x) {
            return dfs(x);
        });
        if (!check) {
            return false;
        }

        // 深搜完成，未发现出现过的节点，安全
        status[v] = 2;
        return true;
    };

    vector<int> res;
    for (int i = 0; i < graph.size(); ++i) {
        if (dfs(i)) {
            res.emplace_back(i);
        }
    }

    return res;
}

/* 拓扑排序 */
vector<int> eventualSafeNodes(vector<vector<int>> &graph) {
    /* 反向考虑：出度为 0 的点为安全节点，建立反向图，入度为 0 的点及后继节点（若入度可以变为 0），则为安全点 */
    int n = graph.size();
    // 反向图
    vector<vector<int>> reverse_graph(n);
    // 每个点的入度
    vector<int> in(n);
    for (int i = 0; i < n; ++i) {
        for (auto &x : graph[i]) {
            reverse_graph[x].emplace_back(i);
        }
        in[i] = graph[i].size();
    }

    // 存储入度为 0 的点
    queue<int> q;
    // 入度为 0 的点先入队列
    for (int i = 0; i < n; ++i) {
        if (in[i] == 0) {
            q.emplace(i);
        }
    }

    while (!q.empty()) {
        int x = q.front();
        q.pop();
        // 将入度为 0 的点的后继节点入度 - 1
        for (auto &y : reverse_graph[x]) {
            // 后继节点入度为 0，加入队列
            if (--in[y] == 0) {
                q.emplace(y);
            }
        }
    }

    vector<int> res;
    // 遍历最终入度为 0 的点，加入结果集
    for (int i = 0; i < n; ++i) {
        if (in[i] == 0) {
            res.emplace_back(i);
        }
    }

    return res;
}

int main() {
    vector<vector<int>> graph = {{1, 2},
                                 {2, 3},
                                 {5},
                                 {0},
                                 {5},
                                 {},
                                 {}};

    vector<int> res = eventualSafeNodes(graph);
    for (auto &x : res) {
        cout << x << " ";
    }
    cout << endl;

    res = eventualSafeNodes_DFS(graph);
    for (auto &x : res) {
        cout << x << " ";
    }
    cout << endl;
}